package com.springchang.algorithm.dynamic;

/**
 * 动态规划解决背包问题
 * @author 张翠山
 * @date : 2021/08/27
 */
public class KnapsackProblem {

    public static void main(String[] args) {
        //商品的价格数组
        int[] v = new int[]{1500, 3000, 2000};
        //商品的重量数组
        int[] w = new int[]{1, 4, 3};
        //商品的价值二维数组
        int[][] values = new int[4][5];

        //给二维数组第一行全部置0
        for (int i = 0; i < 5; i++) {
            values[0][i] = 0;
        }

        //给二维数组第一列全部置0
        for (int i = 0; i < 4; i++) {
            values[i][0] = 0;
        }

        //循环遍历往二维数组中填表
        for (int i = 1; i < 4; i++) {
            for (int j = 1; j < 5; j++) {
                //如果当前新加入的商品质量当前背包的容量，则values等于上一个策略的容量
                if(w[i-1] > j) {
                    values[i][j] = values[i-1][j];
                } else {
                    //如果当前新加入的商品容量小于当前背包的容量，则求最大值
                    values[i][j] = Math.max(values[i-1][j], v[i-1]+values[i-1][j-w[i-1]]); //{上一个最优策略的至, 当前容量+剩余容量的最大值}
                }
            }
        }

        for (int[] value : values) {
            for (int i : value) {
                System.out.print(i+"\t");
            }
            System.out.println();
        }
    }
}
